The present invention relates to a method and apparatus for the generation of confusion data. More particularly, the invention relates to a confusion data generator for generating non-linear confusion data for use with a combiner to store plaintext data on a storage medium or to transmit data over a communication medium in a secure fashion.
In this application, the phrases xe2x80x9capplication of data to a mediumxe2x80x9d or xe2x80x9capplying data to a mediumxe2x80x9d refer to the act of putting the data on a communication medium or mediums, or a storage medium or mediums. This involves the act of generating physical signals (i.e. electrical, electromagnetic, light, or other) which are sent (for a communication medium) or stored (for a storage medium).
Whether data is transmitted or stored, it is susceptible to unauthorized observation. Security is becoming particularly difficult as computers are increasingly networked, thus increasing potential access to stored or transmitted confidential data. Therefore, to transmit or store data in a secure fashion, the data must be encrypted.
One of the main objectives of the field of data encryption is to transform plaintext data into ciphertext data in a way to conceal the information content of the original data. For the transformation to be of any value, it should be reversible, meaning that an inverse transformation should exist that enables the user to obtain the original plaintext from the ciphertext (i.e. decryption). In general, the process involves the use of a secret key in the encryption and decryption phases.
There are many encryption techniques that can be used to transfer plaintext into ciphertext. Such techniques generally utilize block ciphers, substitution ciphers, stream ciphers or random number generators. However, due to the ease of their implementation in software and hardware, stream ciphers have gained popularity as fast encryptor devices. Hence, many popular encryption techniques are based on stream ciphers.
In general, a stream cipher combines plaintext data with pseudo-random confusion data to produce ciphertext data. Hence, a stream cipher can be thought of as a confusion data generator and a combiner. An important combiner is based on the binary bit-by-bit addition mod 2, which is also known as the Boolean logic exclusive-OR (XOR) function. Hence, the confusion data would be combined with the plaintext data by using the XOR function in order to encrypt the plaintext. In the decryption process, the same confusion data would be XORed with the ciphertext data in order to recover the original plaintext.
The design of ciphers must assume that the cipher must be able to confront an unauthorized attacker who seeks the information contained in the ciphertext. In this regard, the use of the XOR function is useful in the encryption process. This is because the task of XORing the plaintext with pseudo-random bytes generally results in the generation of pseudo-random bytes. This helps to disguise the frequency statistics of the plaintext data. Furthermore, the use of the XOR function has the advantage of making the decrypting process simple. This is because it is possible to extract the plaintext from the ciphertext by simply XORing the ciphertext with the confusion data.
The use of the XOR function as a combiner has a major drawback: the use of the XOR function allows an unauthorized analyst to cryptoanalyze the confusion stream. This can be done by using plaintext attacks. If an analyst is able to obtain some amount of plaintext and the matching ciphertext, the analyst can recover that portion of the confusion data. In the worst case scenario, the unauthorized attacker could analyse the confusion data and manage to reproduce the pseudo-random source, thus making the decryption of all subsequent messages possible. Therefore, designers must develop confusion generators or random number generators which are exceedingly difficult for a cryptanalyst to analyse successfully.
Accordingly, an important object of the present invention is to provide a confusion data generator for generating confusion data which is difficult to cryptoanalyze when used with a combiner, such as an XOR combiner.
A second object of the invention is to provide a confusion data generator that is scalable and capable of being implemented in hardware and software of various complexities.
A third object of the invention is to provide a confusion data generator that is fast and therefore computationally inexpensive.
The confusion data generator of the present invention generates non-linear confusion data. In one embodiment, the confusion data generator uses a plurality of arrays, i.e. at least two arrays, acting as non-linear state machines to generate a stream of confusion data made up of blocks of confusion bits. Each non-linear state machine produces sub-blocks of confusion bits and thereby contributes equally to the overall width of the confusion data. The state machines drive each other in a feed forward and feed back fashion. The output bit stream from the confusion data generator is then used with a combiner such as an XOR combiner to generate secure text from plaintext. The confusion data generator can be used to securely store data on a storage medium or transmit data over a communication medium. The confusion data generator is computationally inexpensive, scalable and provides good security when used with a combiner, such as an XOR combiner, to generate secure text.
According to the invention, there is provided a confusion data generator comprising first and second state machines, the second state machine driving the first state machine using data feedback.
According to the invention, there is further provided a confusion data generator comprising: a series of state machines including first and last state machines, each state machine driving the next state machine in the series in a forward fashion, and the last state machine driving the first state machine using data feedback.
According to the invention, there is further provided a non-linear confusion data generator for generating blocks of confusion bits, the confusion data generator comprising: (a) a location counter having a value corresponding to the number of blocks of confusion bits generated; (b) a first array comprising a series of data elements, each of which has a value; (c) a first index having a value corresponding to a data element in the first array; (d) a second index having a value corresponding to a data element in the first array; (e) a second array comprising a series of data elements, each of which has a value; (f) a third index having a value corresponding to a data element in the second array; (g) a fourth index having a value corresponding to a data element in the second array; (h) means for incrementing the value of the location counter; (i) means for updating the value of the first index as a function of the value of the first index, the value of the data element of the first array corresponding to the value of the location counter, and the value of the data element of the second array corresponding to the value of the location counter; (j) means for updating the value of the second index as a function of the value of the data element in the first array corresponding to the value of the first index, and the value of the data element in the first array corresponding to the value of the location counter; (k) means for exchanging the value of the data element in the first array corresponding to the value of the first index and the value of the data element in the first array corresponding to the value of the location counter; (l) means for updating the value of the third index as a function of the value of the third index, the value of the data element of the first array corresponding to value of the location counter, and the value of the data element of the second array corresponding to the value of the location counter; (m) means for updating the value of the fourth index as a function of the value of the data element in the second array corresponding to the value of the third index, and the value of the data element in the second array corresponding to the value of the location counter; (n) means for exchanging the value of the data element in the second array corresponding to the value of the third index and the value of the data element in the second array corresponding to the value of the location counter; (o) means for generating from the first array a first sub-block of confusion bits equal to the value of the data element in the first array corresponding to the value of the second index; (p) means for generating from the second array a second sub-block of confusion bits equal to the value of the data element in the second array corresponding to the value of the fourth index; (q) means for generate corresponding to the first and second sub-blocks of confusion bits; and (r) means for applying the block of confusion bits to a medium.
According to the invention, there is further provided a non-linear confusion data generator for generating blocks of confusion bits, the confusion data generator comprising: (a) a location counter having a value corresponding to the number of blocks of confusion bits generated; (b) a plurality of arrays, each array comprising: (i) a series of data elements, each data element having a value; (ii) a first index having a value corresponding to a data element in the array; and (iii) a second index having a value corresponding to a data element in the array; (c) means for incrementing the value of the location counter; (d) means for updating the value of the first index in each array as a function of the value of the first index of such array, the value of the data element of such array corresponding to the value of the location counter, and the value of the data element of at least one other array corresponding to the value of the location counter; (e) means for updating the value of the second index in each array as a function of the value of the data element in such array corresponding to the value of the first index in such array, and the value of the data element in such array corresponding to the value of the location counter; (f) means for exchanging the value of the data element in each array corresponding to the value of the first index in such array and the value of the data element in such array corresponding to the value of the location counter; (g) means for generating from the each array a sub-block of confusion bits equal to the value of the data element in such array corresponding to the value of the second index in such array; (h) means for generating a block of confusion bits comprising the sub-blocks of confusion bits generated by the arrays; and (i) means for applying the block of confusion bits to a medium.
According to the invention, there is further provided a method for generating blocks of confusion bits, the method utilizing a non-linear confusion data generator comprising: a location counter having a value corresponding to the number of blocks of confusion bits generated; a first array comprising a series of data elements, each of which has a value; a first index having a value corresponding to a data clement in the first array; a second index having a value corresponding to a data element in the first array; a second array comprising a series of data elements, each of which has a value; a third index having a value corresponding to a data element in the second array; and a fourth index having a value corresponding to a data element in the second array; the method comprising: (a) incrementing the value of the location counter; (b) updating the value of the first index as a function of the value of the first index, the value of the data element of the first array corresponding to the value of the location counter, and the value of the data element of the second array corresponding to the value of the location counter; (c) updating the value of the second index as a function of the value of the data element in the first array corresponding to the value of the first index, and the value of the data element in the first array corresponding to the value of the location counter; (d) exchanging the value of the data element in the first array corresponding to the value of the first index and the value of the data element in the first array corresponding to the value of the location counter; (e) updating the value of the third index as a function of the value of the third index, the value of the data element of the first array corresponding to value of the location counter, and the value of the data element of the second array corresponding to the value of the location counter; (f) updating the value of the fourth index as a function of the value of the data element in the second array corresponding to the value of the third index, and the value of the data element in the second array corresponding to the value of the location counter; (g) exchanging the value of the data element in the second array corresponding to the value of the third index and the value of the data element in the second array corresponding to the value of the location counter; (h) the first array generating a first sub-block of confusion bits equal to the value of the data element in the first array corresponding to the value of the second index; (i) the second array generating a second sub-block of confusion bits equal to the value of the data element in the second array corresponding to the value of the fourth index; (j) generating a block of confusion bits comprising the first and second sub-blocks of confusion bits; and (k) applying the block of confusion bits to a medium.
According to the invention, there is further provided a method for generating blocks of confusion bits, the method utilizing a non-linear confusion data generator comprising: a location counter having a value corresponding to the number of blocks of confusion bits generated; a plurality of arrays, each array comprising a series of data elements, each data element having a value a first index having a value corresponding to a data element in the array and a second index having a value corresponding to a data element in the array; (a) incrementing the value of the location counter; (b) updating the value of the first index in each array as a function of the value of the first index of such array, the value of the data element of such array corresponding to the value of the location counter, and the value of the data element of at least one other array corresponding to the value of the location counter; (c) updating the value of the second index in each array as a function of the value of the data element in such array corresponding to the value of the first index in such array, and the value of the data element in such array corresponding to the value of the location counter; (d) exchanging the value of the data element in each array corresponding to the value of the first index in such array and the value of the data element in such array corresponding to the value of the location counter; (e) generating from the each array a sub-block of confusion bits equal to the value of the data element in such array corresponding to the value of the second index in such array; (f) generating a block of confusion bits comprising the sub-blocks of confusion bits generated by the arrays; and (g) applying the block of confusion bits to a medium.
Among the advantages of the present invention are that the confusion data generator of the present invention: generates highly non-linear or complex confusion data that is difficult to cryptoanalyze (whether used with an XOR combiner or another combiner); is scalable and capable of being implemented in hardware and software of various complexities; and is fast and therefore computationally inexpensive.
Other advantages, objects and features of the present invention will be readily apparent to those skilled in the art from a review of the following detailed description of preferred embodiments in conjunction with the accompanying drawings and claims.